<?php

/**
 * Finding the lowest common ancestor of two nodes in a BST
 * Algo: in a top down traverse:
 * 1) if two nodes less than the current node, LCA exists in the left BST
 * 2) if two nodes greater than the current node, LCA exists in the right BST
 * 3) if two nodes lays as each on both side, because "top down", this should be the LCA
 * 4) if current node is one of the nodes, this is the LCA
 */


require_once 'util.php';

importJS();

$arr = generateRandomArray(0, 99, 7);
$value1 = $arr[3];
$value2 = $arr[5];

var_dump($arr);

$root = null;
foreach( $arr as $value ){
	$root = bst_insert($value, $root);
}

//bt_print_inorder($root);
//bt_draw($root);
bt_draw( $root );

echo "<br/>";

$node = bst_lowest_common_ancestor($root, $value1, $value2);
echo "{$node->value} is the LCA of $value1 and $value2<br/>";

function bst_lowest_common_ancestor( $root, $value1, $value2 ){
	if( !$root ){
		return;
	}

	// Assuming $value1, $value2 are inside the BST
	$value = $root->value;
	if( $value1 < $value && $value2 < $value ){
		return bst_lowest_common_ancestor( $root->left, $value1, $value2 );
	}
	else if( $value1 > $value && $value2 > $value ){
		return bst_lowest_common_ancestor( $root->right, $value1, $value2 );
	}
	else if( ( $value1 < $value && $value2 > $value ) || ( $value1 > $value && $value2 < $value ) ){
		return $root;
	}
	else if( $value1 == $value || $value2 == $value ){
		return $root;
	}

}


